package com.Leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class FloodFill {
	public static void main(String[] args) {
		int[][] a = new int[][] {{0,0,0},{0,0,0}};
		FloodFill f = new FloodFill();
		System.out.println(f.floodFill(a, 0, 0, 2));
	}
	Queue<int[]> q;
	int[][] flag;
	public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        q = new LinkedList<>();
        flag = new int[image.length][image[0].length];
        int oldColor = image[sr][sc];
        flag[sr][sc] = 1;
        image[sr][sc] = newColor;
        q.offer(new int[]{sr,sc});
		while(!q.isEmpty()) {
			int[] a = q.poll();
			int i = a[0];
			int j = a[1];
			check(image,i,j,newColor,oldColor);
		}
		return image;
    }
	
	public void check(int[][] image,int i,int j,int newColor,int oldColor) {
		if(i - 1 >= 0 && image[i - 1][j] == oldColor && flag[i - 1][j] != 1){
			image[i - 1][j] = newColor;
			q.offer(new int[] {i - 1,j});
			flag[i - 1][j] = 1;
		}
		if(j - 1 >= 0 && image[i][j - 1] == oldColor && flag[i][j - 1] != 1){
			image[i][j - 1] = newColor;
			q.offer(new int[] {i,j - 1});
			flag[i][j - 1] = 1;
		}
		if(i + 1 < image.length && image[i + 1][j] == oldColor && flag[i + 1][j] != 1){
			image[i + 1][j] = newColor;
			q.offer(new int[] {i + 1,j});
			flag[i + 1][j] = 1;
		}
		if(j + 1 < image[0].length && image[i][j + 1] == oldColor && flag[i][j + 1] != 1){
			image[i][j + 1] = newColor;
			q.offer(new int[] {i,j + 1});
			flag[i][j + 1] = 1;
		}
	}
}
